//
// Created by Lenovo on 2021/12/26.
//

#include "Link_BiTree.h"

///////////////////////////////////////////////////BITREE///////////////////////////////////////////////////////////////

char CreateData(TElemType data){
    return data;
}//用于创建数据赋值给树节点的值域

int NumOfNode(BiTree T){
    if(T!=NULL)
        return NumOfNode(T->lchild)+ NumOfNode(T->rchild);
    else
        return 0;
}//返回此二叉树中结点的个数

Status InitBiTree(BiTree T){
    T->data= CreateData('\0');   //根节点的数据清零
    T->rchild=NULL; //左右孩子初始化
    T->rchild=NULL;
    return OK;
}    //初始化树，构造空二叉树

//版本一：
//Status DestroyBiTree_(BiTree T){
//    if(T->lchild!=NULL){    //如果当前结点的左孩子不为空，递归进入左孩子，销毁后给左孩子置空
//        DestroyBiTree_(T->lchild);
//        T->lchild=NULL;
//    }
//    if(T->rchild!=NULL){    //同理
//        DestroyBiTree_(T->rchild);
//        T->rchild=NULL;
//    }
//    if(T->rchild==NULL&&T->lchild==NULL){   //左右孩子都空，释放当前结点
//        free(T);
//        T=NULL;
//        return OK;
//    }
//    return OK;
//} //销毁二叉树，初始条件：二叉树已存在
//
//Status DestroyBiTree(BiTree *T){
//    DestroyBiTree_(*T);
//    (*T)=NULL;
//    return OK;
//} //销毁二叉树，初始条件：二叉树已存在

//版本二：
Status DestroyBiTree(BiTree *T){
    if((*T)->lchild!=NULL){    //如果当前结点的左孩子不为空，递归进入左孩子，销毁后给左孩子置空
        DestroyBiTree(&(*T)->lchild);
//        T->lchild=NULL;
    }
    if((*T)->rchild!=NULL){    //同理
        DestroyBiTree(&(*T)->rchild);
//        T->rchild=NULL;
    }
    if((*T)->rchild==NULL&&(*T)->lchild==NULL){   //左右孩子都空，释放当前结点
        free(*T);
        (*T)=NULL;
        return OK;
    }
    return OK;
} //销毁二叉树，初始条件：二叉树已存在

//CreateBiTree(BiTree T,definition);    //definition为构造二叉树的定义，按照定义构造二叉树

//按先序序列建立二叉树
int CreateBiTree(BiTree *T){
    char ch;
    scanf("%c", &ch);   //读入字符
    if (ch=='.')	(*T) = NULL;    //如果为‘.’，此节点为空
    else {
        if (!( (*T) = (BiTNode *)malloc(sizeof(BiTNode))))	exit(OVERFLOW);
        (*T)->data = ch;              // 生成根结点
        CreateBiTree(&((*T)->lchild));   // 构造左子树
        CreateBiTree(&((*T)->rchild));   // 构造右子树
    }
    return OK;
}//CreateBiTree


Status ClearBiTree(BiTree *T){
    if((*T)==NULL) return ERROR;   //如果树不存在，返回ERROR

    //如果根节点的左右孩子均为空，说明树已经清空
    if((*T)->rchild==NULL&&(*T)->lchild==NULL){
        (*T)->data='\0';//根节点数据清零
        return OK;
    }
    BiTNode** Ptmp=T;    //创建临时指针

    Stack BiTreeStack;  //创建用于存储树节点的栈
    StackInit(&BiTreeStack);

    int flag=1; //判断临时指针不为根节点的辅助标记，防止将根节点也释放
    while ((*Ptmp)!=(*T)||flag){
        flag=0; //仅第一次有效
        PushBiTree(&BiTreeStack,(*Ptmp));  //结点入栈
        if((*Ptmp)->lchild!=NULL){ //如果当前结点的左孩子不为空，指针更新为左孩子并且跳到下一个循环
            (*Ptmp)=(*Ptmp)->lchild;
            continue;
        } else if((*Ptmp)->rchild!=NULL){//如果当前结点的右孩子不为空，指针更新为左孩子并且跳到下一个循环
            (*Ptmp)=(*Ptmp)->rchild;
            continue;
        } else{ //如果左右孩子都为空，将栈顶元素出栈，并且释放当前结点空间并置空，将临时指针指向栈顶元素
            PopBiTree(&BiTreeStack);
            free((*Ptmp));
            (*Ptmp)=NULL;
            (*Ptmp)= GetTop(BiTreeStack);
        }
    }
}   //将二叉树清为空树，初始条件：二叉树已存在


Status BiTreeEmpty(BiTNode T){
    if(T.data!='\0'||T.rchild!=NULL||T.lchild!=NULL)
        return FALSE;
    else
        return TRUE;
}  //若二叉树为空返回TRUE，否则返回FALSE


Status BiTreeDepth(const BiTree T){
    return (log(NumOfNode(T))/ log(2))+1;
}  //获取二叉树的深度，初始条件：二叉树已存在


BiTree Root(BiTNode T){

} //获取二叉树的根节点，初始条件：二叉树已存在


TElemType Value(BiTNode T,BiTNode* e){

}    //返回e中的结点数据，初始条件：二叉树T已存在，e为二叉树中的结点


Status Assign(BiTree T,BiTNode* e,TElemType value){

}  //将结点e的值赋值为value，初始条件：二叉树T存在，e为二叉树中的结点


BiTNode* Parent(BiTree T , BiTNode* e){
    if(T==NULL||T->lchild==NULL||T->rchild==NULL)
        return NULL;
    if(T->rchild==e||T->lchild==e)
        return T;
    else{
        BiTNode* tmp= Parent(T->lchild,e);
        if(tmp) return tmp;
        else{
            tmp= Parent(T->rchild,e);
            if(tmp) return tmp;
            else return NULL;
        }
    }
} //若e是二叉树的非根结点，返回它的双亲，否则返回NULL


BiTNode* LeftChild(BiTree T,BiTNode* e){

} //返回e的左孩子，没有左孩子返回空，初始条件：二叉树存在，e是二叉树的结点


BiTNode* RightChild(BiTree T,BiTNode* e){

}    //返回e的右孩子，没有右孩子返回空，初始条件：二叉树存在，e是二叉树的结点


BiTNode* LeftSibling(BiTree T,BiTNode* e){

}   //返回e的左兄弟，若e为T的左孩子或无左兄弟，返回空，初始条件：二叉树T存在，e是二叉树中的结点


BiTNode* RightSibling(BiTree T,BiTNode* e){

} //返回e的右兄弟，若e为T的右孩子或无右兄弟，返回空，初始条件：二叉树存在，e是二叉树中的结点

Status InsertChild(BiTree T,BiTNode* p,int LR,BiTNode* C){

}  //根据LR为0或1，插入C为T中p所指结点的左或右子树，p所指系欸但的原有左或右子树则成为C的右子树
//初始条件，二叉树T存在，p指向T中某一个结点，LR为0或1，非空二叉树不与T相交并且右子树为空


BiTNode DeleteChild(BiTree T,BiTNode* p,int LR){

}    //根据LR为0或1，删除T中p所指结点的左或右子树


//先序遍历二叉树(递归)
void PreOrderTraverse(BiTree T, int (* Visit)(char e)){
    if (T) {
        Visit(T->data);	//访问根结点
        PreOrderTraverse(T->lchild, Visit);	//先序遍历左子树
        PreOrderTraverse(T->rchild, Visit);	//先序遍历右子树
    }
}//PostOrderTraverse


void InOrderTraverse(BiTree T,int (*visit)(TElemType e)){
    if (T) {
        PreOrderTraverse(T->lchild, visit);	//中序遍历左子树
        visit(T->data);	//访问根结点
        PreOrderTraverse(T->rchild, visit);	//中序遍历右子树
    }
}//中序遍历


//后序遍历二叉树(递归)
void PostOrderTraverse(BiTree T, int (* Visit)(char e)){
    if (T) {
        PostOrderTraverse(T->lchild, Visit);	//后序遍历左子树
        PostOrderTraverse(T->rchild, Visit);	//后序遍历右子树
        Visit(T->data);	//访问根结点
    }
}//PostOrderTraverse


void LevelOrderTraverse(BiTree  T,int (*visit)(TElemType e)){

}//层次遍历


Status Whether_E_InBiTree(BiTree T,BiTNode* e){
    if(T==e)
        return 1;
    if (T) {
        int flag=  Whether_E_InBiTree(T->lchild,e);
        if(flag)    return flag;
        else{
            flag=Whether_E_InBiTree(T->rchild,e);
            if(flag)    return flag;
        }
    }
    return 0;

}//结点e是否在T中；

////////////////////////////////////////////////////////TREE STACK//////////////////////////////////////////////////////

Status StackInit(Stack* st){
    st->Stacksize=0;
    st->top=NULL;
    st->base=NULL;
//    printf("List Stack Initiate Success!\n");
}//List Stack Initiate

Status PushBiTree(Stack* sta,BiTree data){
    Ele* e =(Ele*) malloc(sizeof(Ele));
    if(e==NULL) exit(-1);
    e->data=data;
    e->pre=sta->top;
    if(sta->Stacksize==0) sta->base=e;
    sta->top=e;
    sta->Stacksize++;
//    printf("Element In Stack Success!\n");
}//Element In Stack

BiTree PopBiTree(Stack* sta){
    BiTree data;
    if(sta->Stacksize==0&&sta->top==sta->base)
        exit(-1);
    data=sta->top->data;
    Ele* tmp=sta->top;
    sta->top=sta->top->pre;
    tmp->pre=NULL;
    free(tmp);
    sta->Stacksize--;
//    printf("Element Out Stack Success!\n");
    return data;
}//Element Out Stack

Status DestroyStack(Stack *sta){
    while (sta->Stacksize>0)
        PopBiTree(sta);
    sta->top=NULL;
    sta->base=NULL;
//    printf("Destroy List Stack Success!\n");
}//Destroy List Stack

Status ClearStack(Stack* sta){
    while (sta->Stacksize>0)
        PopBiTree(sta);
//    printf("Clear Stack Success!\n");
}//Clear Stack

Status StackEmpty(Stack sta){
    if(sta.Stacksize!=0)
        return FALSE;
    else
        return TRUE;
}//Judge Stack Whether Empty

int StackLength(Stack sta){
    return sta.Stacksize;
}//Get the length of Stack


BiTree   GetTop(Stack sta){
    return sta.top->data;
}//Get the top Element of Stack

Status StackTraverse(Stack sta,Status (*visit)(BiTree)){
    if(sta.top==NULL||sta.base==NULL||sta.top==sta.base||sta.Stacksize==0)
        return ERROR;
    Ele * Ptmp=sta.top;
    TraverseBaseToTop(Ptmp,visit);
}//Traverse Stack

Status TraverseBaseToTop(Ele* Ptmp,Status (*visit)(BiTree)){
    if(Ptmp==NULL)
        return ERROR;
    else{
        TraverseBaseToTop(Ptmp->pre,visit);
        (*visit)(Ptmp->data);
    }
    return OK;
}

//////////////////////////////////////////////////TAG STACK/////////////////////////////////////////////////////////////

Status TAGStackInit(TAGStack* st){
    st->Stacksize=0;
    st->top=NULL;
    st->base=NULL;
//    printf("初始化正常\n");
}//链栈初始化

Status TAGStackIn(TAGStack* sta,int  data){
    TAGEle* e =(TAGEle*) malloc(sizeof(TAGEle));
    if(e==NULL) exit(-1);
    e->data=data;
    e->pre=sta->top;
    if(sta->Stacksize==0) sta->base=e;
    sta->top=e;
    sta->Stacksize++;
//    printf("Data In Stack Successful!\n");
}//元素入栈

int TAGStackOut(TAGStack* sta){
    int data;

    if(sta->Stacksize==0&&sta->top==sta->base)
        exit(-1);
    data=sta->top->data;
    TAGEle* tmp=sta->top;
    sta->top=sta->top->pre;
    tmp->pre=NULL;
    free(tmp);
    sta->Stacksize--;
//    printf("Data Out Stack Successful!\n");
    return data;
}//元素出栈

Status TAGStackEmpty(TAGStack sta){
    if(sta.Stacksize!=0)
        return FALSE;
    else
        return TRUE;
}//判断栈是否为空

int TAGGetTop(TAGStack sta){
    return sta.top->data;
}//获取栈顶元素

Status TAGSetTopData(TAGStack* s,int Ndata){
    s->top->data=Ndata;
    return OK;
}//设置栈顶元素值